home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 039a / bplus25a.zip / CPLUS.C < prev    next >
Text File  |  1990-12-30  |  40KB  |  1,049 lines
  1. /********************************************************************/
  2. /*                                                                  */
  3. /*             BPLUS file indexing program - Version 2.5            */
  4. /*                                                                  */
  5. /*                      A "shareware program"                       */
  6. /*                                                                  */
  7. /*                                                                  */
  8. /*                    Copyright (C) 1987-1990 by                    */
  9. /*                                                                  */
  10. /*                      Hunter and Associates                       */
  11. /*                      7900 Edgewater Drive                        */
  12. /*                      Wilsonville, Oregon  97070                  */
  13. /*                      (503) 694 - 1449                            */
  14. /*                                                                  */
  15. /********************************************************************/
  16.  
  17.  
  18. #include <stdio.h>
  19. #include <fcntl.h>
  20. #include <io.h>
  21. #include <process.h>
  22. #include <sys\types.h>            /*  delete this line for Turbo C  */
  23. #include <sys\stat.h>
  24. #include <string.h>
  25. #include "bplus.h"
  26.  
  27.  
  28. /*  macros, constants, data types  */
  29.  
  30. #define  NULLREC      (-1L)  /* special value for RECPOS variable */
  31. #define  FREE_BLOCK   (-2)   /* designates a free block in index file */
  32.         /* the address of an entry in a block */
  33. #define  ENT_ADR(pb,off)  ((ENTRY*)((char*)((pb)->entries) + off))
  34.         /* the size of an entry */
  35. #define  ENT_SIZE(pe)     strlen((pe)->key) + 1 + 2 * sizeof(RECPOS)
  36.         /* the cache changed indicator */
  37. #define  BUFDIRTY(j)      (mci->cache[j].dirty)
  38.         /* the index file handle for memblock j */
  39. #define  BUFHANDLE(j)     (mci->cache[j].handle)
  40.         /* memory cache block j */
  41. #define  BUFBLOCK(j)      (mci->cache[j].mb)
  42.         /* number of times cache blk j is referenced */
  43. #define  BUFCOUNT(j)      (mci->cache[j].count)
  44.         /* address of current block for level j */
  45. #define  CB(j)            (pci->pos[j].cblock)
  46.         /* offset of current block for level j */
  47. #define  CO(j)            (pci->pos[j].coffset)
  48. #define  TRUE             1
  49. #define  FALSE            0
  50.  
  51.  
  52. /*  declare some global variables  */
  53.  
  54. IX_DESC      *pci;                       /* pointer to index descriptor   */
  55. IX_BUFFER    bt_buffer;                  /* memory cache for index blocks */
  56. IX_BUFFER    *mci = &bt_buffer;          /* pointer to cache index blocks */
  57. BLOCK        *block_ptr;                 /* pointer to index record block */
  58. BLOCK        *spare_block;               /* pointer to spare index block  */
  59. int          cache_ptr = 0;              /* index to cache memory pool    */
  60. int          cache_init = 0;             /* 1 when cache is initilized    */
  61. int          split_size = IXB_SPACE;     /* split block when greater than */
  62. int          comb_size  = (IXB_SPACE/2); /* combine blocks when less than */
  63.  
  64. /* #define memmove     memcpy */    /* Use this macro for MicroSoft C 4.0 */
  65.  
  66. /* list all function prototypes */
  67. void pascal error(int, long);
  68. void pascal read_if(long, char *, int);
  69. void pascal write_if(int, long, char *, int);
  70. int  pascal creat_if(char *);
  71. int  pascal open_if(char *);
  72. void pascal reset_buffers(IX_DESC *);
  73. void pascal close_if(int);
  74. void pascal update_block(void);
  75. void pascal init_cache(void);
  76. int  pascal find_cache(RECPOS);
  77. int  pascal new_cache(void);
  78. void pascal load_cache(RECPOS);
  79. void pascal get_cache(RECPOS);
  80. void pascal retrieve_block(int, RECPOS);
  81. int  pascal prev_entry(int);
  82. int  pascal next_entry(int);
  83. void pascal copy_entry(ENTRY *, ENTRY *);
  84. int  pascal scan_blk(int);
  85. int  pascal last_entry(void);
  86. void pascal write_free( RECPOS, BLOCK *);
  87. RECPOS pascal get_free(void);
  88. int  pascal find_block(ENTRY *, int *, int *);
  89. void pascal movedown(BLOCK *, int, int);
  90. void pascal moveup(BLOCK *, int, int);
  91. void pascal ins_block(BLOCK *, ENTRY *, int);
  92. void pascal del_block(BLOCK *, int);
  93. void pascal split(int, ENTRY *, ENTRY *);
  94. void pascal ins_level(int, ENTRY *);
  95. int  pascal insert_ix(ENTRY *, IX_DESC *);
  96. int  pascal find_ix(ENTRY *, IX_DESC *, int);
  97. int  pascal combineblk(RECPOS, int);
  98. void pascal replace_entry(ENTRY *);
  99.  
  100.  
  101. /*  file I/O for B-PLUS module  */
  102.  
  103. void pascal error(j, l)               /* print file error messages */
  104.   int j;                              /* error number */
  105.   long l;                             /* current file position */
  106.   {
  107.     static char *msg[3] = {"ERROR - CANNOT OPEN/CLOSE FILE",
  108.                            "ERROR WHILE READING FILE",
  109.                            "ERROR WHILE WRITING FILE"};
  110.     printf("\n  %s - Record Number %ld\n", msg[j], l);
  111.     exit(1);                  /* delete this line to not halt program */
  112.                               /* and call your error handlng routine */
  113.   } /* error */
  114.  
  115.  
  116. void pascal read_if(start, buf, nwrt)    /* read pci index file */
  117.   long start;                            /* file read position */
  118.   char *buf;                             /* data holding buffer */
  119.   int nwrt;                              /* number bytes to read */
  120.   {
  121.     long err;
  122.           /* seek to read position in current index file */
  123.     err = start - lseek(pci->ixfile, start, SEEK_SET);
  124.          /* if no error read an index file block */
  125.     if (err == 0) err = nwrt - read(pci->ixfile, buf, nwrt);
  126.          /* call error routine if number bytes read != nwrt */
  127.     if (err != 0) error(1, start);
  128.   } /* read_if */
  129.  
  130.  
  131. void pascal write_if(handle, start, buf, nwrt)   /* write index record */
  132.   int handle;                        /* write to this file handle */
  133.   long start;                        /* write to this position in file */
  134.   char *buf;                         /* write data from this buffer */
  135.   int nwrt;                          /* write this many bytes of data */
  136.   {
  137.     long err;
  138.          /* seek to file write position */
  139.     err = start - lseek(handle, start, SEEK_SET);
  140.          /* if no error write index block block */
  141.     if (err == 0) err = nwrt - write(handle, buf, nwrt);
  142.          /* call error routine if number bytes written != nwrt */
  143.     if (err != 0) error(2, start);
  144.   } /* write_if */
  145.  
  146.  
  147. int pascal creat_if(fn)               /* make a new index file */
  148.   char *fn;                           /* name and path of file */
  149.   {
  150.     int   ret;
  151.     ret = open(fn,O_RDWR|O_CREAT|O_TRUNC|O_BINARY,S_IWRITE);
  152.     if (ret  < 0) error(0,0L);        /* there was an error if ret < 0 */
  153.     return (ret);
  154.   } /* creat_if */
  155.  
  156.  
  157. int pascal open_if(fn)                /* open an existing index file */
  158.   char *fn;                           /* path and name of index file */
  159.   {
  160.     int  ret;
  161.     ret = open(fn,O_RDWR|O_BINARY);
  162.     if (ret < 1) error(0,0L);         /* there was an error is ret < 1 */
  163.     return (ret);
  164.   } /* open_if */
  165.  
  166.  
  167. void pascal close_if(handle)          /* close an open index file */
  168.   int handle;                         /* with this file handle    */
  169.   {
  170.     if(close(handle) < 0)  error(2,0L);
  171.   } /*  close_if */
  172.  
  173.  
  174. int cdecl open_index(name, pix, dup)  /* open and initilize index file */
  175.   char *name;                         /* path and name of index file */
  176.   IX_DESC *pix;                       /* pointer to index descriptor */
  177.   int dup;                            /* allow duplicate keys if != 0 */
  178.   {
  179.     pci = pix;                        /* pci is global index descriptor */
  180.     pci->ixfile = open_if(name);      /* file handle */
  181.     pci->duplicate = dup;             /* set duplicate keys flag */
  182.     pci->root_dirty = FALSE;
  183.      /* read root descriptor for index */
  184.     read_if(0L,(char *)&(pix->root), (sizeof(BLOCK) + sizeof(IX_DISK)));
  185.     if (!cache_init)                   /* if cache not initilized */
  186.       {
  187.         init_cache();                  /* initilize cache memory */
  188.         cache_init = 1;                /* but only once */
  189.       }
  190.     return ( IX_OK );
  191.   } /* open_index */
  192.  
  193.  
  194. void cdecl buffer_flush(pix)         /* flushes internal index buffers */
  195.   IX_DESC *pix;
  196. {
  197.   int i;
  198.   if (pix->root_dirty)
  199.   {
  200.     write_if(pix->ixfile, 0L,(char *)&(pix->root),
  201.                (sizeof(BLOCK) + sizeof(IX_DISK)));
  202.     pix->root_dirty = FALSE;
  203.   }
  204.   for (i = 0; i < NUM_BUFS; i++)
  205.   {
  206.     if ( (BUFHANDLE(i) == pix->ixfile) && BUFDIRTY(i) )
  207.     {
  208.       write_if(BUFHANDLE(i),
  209.            BUFBLOCK(i).brec,
  210.            (char *) &BUFBLOCK(i),
  211.            sizeof(BLOCK));
  212.       BUFDIRTY(i) = FALSE;
  213.     }
  214.   }
  215. }
  216.  
  217. void pascal reset_buffers(pix)
  218.   IX_DESC *pix;
  219.   {
  220.     int i;
  221.     for (i = 0; i < NUM_BUFS; i++)
  222.       if (BUFHANDLE(i) == pix->ixfile) BUFBLOCK(i).brec = NULLREC;
  223.   }
  224.  
  225.  
  226. int cdecl close_index(pix)           /* close index file */
  227.   IX_DESC *pix;
  228.   {
  229.     int ret = IX_OK;
  230.     buffer_flush(pix);
  231.       reset_buffers(pix);
  232.     close_if(pix->ixfile);
  233.     return( ret );
  234.   } /* close_index */
  235.  
  236.  
  237.  
  238. int cdecl make_index(name, pix, dup)       /* create a new index file */
  239.   char *name;                        /* pointer to path and file name */
  240.   IX_DESC *pix;                      /* pointer to index descriptor */
  241.   int dup;                           /* duplicate keys allow is != 0 */
  242.   {
  243.     pci = pix;             /* set global pci to this index descriptor */
  244.     pci->ixfile = creat_if(name);
  245.     pci->root_dirty = FALSE;
  246.     pci->duplicate = dup;
  247.     pci->dx.nl = 1;               /* the only block is the root */
  248.     pci->dx.ff = NULLREC;         /* there are no free index blocks */
  249.     pci->level = 0;               /* the root is level 0 */
  250.     CO(0) = -1;                   /* the current block offset is -1 */
  251.     CB(0) = 0L;                   /* the current block address 0L */
  252.     pci->root.brec = 0L;          /* root block address is 0L */
  253.     pci->root.bend = 0;           /* no entries yet so block end is 0 */
  254.     pci->root.p0 = NULLREC;       /* p0 points to next index level */
  255.  
  256.          /* write the root block of the index descriptor */
  257.     write_if(pci->ixfile, 0L,(char *)&(pix->root),
  258.                (sizeof(BLOCK) + sizeof(IX_DISK)));
  259.     if (!cache_init)
  260.       {                        /* initiate memory cache but only once */
  261.         init_cache();
  262.         cache_init = 1;
  263.       }
  264.     return ( IX_OK );
  265.   } /* make_index */
  266.  
  267.  
  268. /*  cache I/O for BPLUS  */
  269.  
  270.  
  271. void pascal update_block()
  272.   {
  273.    /* set flag that a memory block has changed     */
  274.     if (block_ptr == &(pci->root)) pci->root_dirty = TRUE;
  275.     else  BUFDIRTY(cache_ptr) = TRUE;
  276.   } /* update_block */
  277.  
  278.  
  279. void pascal init_cache()       /* initialize the cache memory buffers */
  280.   {
  281.     register int  j;
  282.     for (j = 0; j < NUM_BUFS; j++)
  283.       {  BUFDIRTY(j) = 0;          /* the buffer has not been changed */
  284.          BUFCOUNT(j) = 0;                /* number of references is 0 */
  285.          BUFBLOCK(j).brec = NULLREC;    /* each memory block is empty */
  286.       }
  287.   } /* init_cache */
  288.  
  289.  
  290. int pascal find_cache(r)          /* find a block in the cache memory */
  291.   RECPOS r;
  292.   {
  293.     register int  j;
  294.     for (j = 0; j < NUM_BUFS; j++)    /* repeat for each index buffer */
  295.       {
  296.              /* check handle and index address for a match */
  297.         if((BUFBLOCK(j).brec == r) && (BUFHANDLE(j) == pci->ixfile))
  298.          {  cache_ptr = j;            /* if match, set cache_ptr */
  299.             return (1);               /* and return true */
  300.       }  }
  301.     return (-1);               /* return false if not in cache memory */
  302.   } /* find_cache */
  303.  
  304.  
  305. int pascal new_cache()             /* assign a block in cache memory */
  306.   {
  307.     register int  i;
  308.     i = (cache_ptr + 1) % NUM_BUFS;    /* assign memory buffer */
  309.          /* if it has been changed, save it to disk */
  310.     if (BUFDIRTY(i)) write_if(BUFHANDLE(i),
  311.                               BUFBLOCK(i).brec,
  312.                               (char *) &BUFBLOCK(i),
  313.                               sizeof(BLOCK));
  314.     BUFHANDLE(i) = pci->ixfile;        /* save index file handle */
  315.     BUFDIRTY(i) = 0;                   /* buffer change flag is false */
  316.     return (i);                        /* return memory buffer pointer */
  317.   } /* new_cache */
  318.  
  319.  
  320. void pascal load_cache(r)         /* load index block in cache memory */
  321.   RECPOS r;
  322.   {
  323.     cache_ptr = new_cache();        /* get a block in cache memory */
  324.                                     /* and then load the index block */
  325.     read_if(r, (char *)&BUFBLOCK(cache_ptr), sizeof(BLOCK));
  326.   } /* load_cache */
  327.  
  328.  
  329. void pascal get_cache(r)            /* load an index block into cache */
  330.   RECPOS r;
  331.   {
  332.     if (find_cache(r) < 0)         /* if block is not in cache memory */
  333.        load_cache(r);              /* load the block in memory */
  334.                                    /* and set block point to this block */
  335.     block_ptr = &BUFBLOCK(cache_ptr);
  336.   } /* get_cache */
  337.  
  338.  
  339. void pascal retrieve_block(j, r)    /* load an index block */
  340.   int j;
  341.   RECPOS r;
  342.   {
  343.     if (j == 0)                     /* if the block wanted is the root */
  344.        block_ptr = &(pci->root);    /* then point to the root */
  345.     else  get_cache(r);             /* else get from cache memory */
  346.     CB(j) = block_ptr->brec;        /* store index block address */
  347.   } /* retrieve_block */
  348.  
  349.  
  350. /*  low level functions of BPLUS  */
  351.  
  352. int pascal prev_entry(off)        /* back up one entry in current block */
  353.   int off;
  354.   {
  355.      if (off <= 0)                /* if off <= can not back up */
  356.        {
  357.          off = -1;                /* set to beginning of block */
  358.          CO(pci->level) = off;
  359.        }
  360.      else
  361.        off = scan_blk(off);       /* find previous entry */
  362.      return(off);
  363.   } /* prev_entry */
  364.  
  365.  
  366. int pascal next_entry(off)        /* find next entry in current block */
  367.   int off;
  368.   {
  369.      if (off == -1)               /* at beginning of the block */
  370.        off = 0;
  371.      else                         /* move to next entry if not at end */
  372.        {
  373.          if (off < block_ptr->bend)
  374.             off += ENT_SIZE(ENT_ADR(block_ptr,off));
  375.        }
  376.      CO(pci->level) = off;       /* save the offset position in block */
  377.      return (off);
  378.   } /* next_entry */
  379.  
  380.  
  381. void pascal copy_entry(to, from)  /* copy an entry */
  382.   ENTRY *to;                     /* to here */
  383.   ENTRY *from;                   /* from here */
  384.   {
  385.     int me;
  386.     me = ENT_SIZE(from);         /* get the entry's size */
  387.     memmove(to, from, me);        /* and copy */
  388.   } /* copy_entry */
  389.  
  390.  
  391. int pascal scan_blk(n)           /* find the offset of last entry in */
  392. int n;                           /* current block before postion n */
  393.   {
  394.      register int off, last;
  395.      off = 0;
  396.      last = -1;
  397.      while (off < n )            /* repeat until position >= n */
  398.        {  last = off;
  399.           off += ENT_SIZE(ENT_ADR(block_ptr,off));
  400.        }
  401.      CO(pci->level) = last;      /* save new block offset positioon */
  402.      return (last);
  403.   } /* scan_blk */
  404.  
  405.  
  406. int pascal last_entry()          /* find offset of last entry in block */
  407.   {
  408.      return( scan_blk(block_ptr->bend) );
  409.   } /* last_entry */
  410.  
  411.  
  412. /*  maintain list of free index blocks  */
  413.  
  414. void pascal write_free(r, pb)    /* update list of free index blocks */
  415.   RECPOS r;                      /* free index position */
  416.   BLOCK *pb;                     /* free block */
  417.   {
  418.     pb->p0 = FREE_BLOCK;         /* mark as free */
  419.     pb->brec = pci->dx.ff;       /* keep old first free address */
  420.     write_if(pci->ixfile, r, (char *) pb, sizeof(BLOCK));
  421.     pci->dx.ff = r;              /* set first free address to r */
  422.   } /* write_free */
  423.  
  424.  
  425. RECPOS pascal get_free()         /* get address of free index block */
  426.   {
  427.     RECPOS  r, rt;
  428.  
  429.     r = pci->dx.ff;              /* use block address ff if free */
  430.     if ( r != NULLREC )
  431.       {  read_if(r, (char *)&rt, sizeof( RECPOS ));
  432.          pci->dx.ff = rt;        /* save next free index block */
  433.       }
  434.     else                         /* else add to end of index file */
  435.       r = filelength (pci->ixfile);
  436.     return (r);                  /* return index block address */
  437.   } /* get_free */
  438.  
  439.  
  440. /*  general BPLUS block level functions  */
  441.  
  442.  
  443. int pascal find_block(pe, off, poff)
  444.   ENTRY *pe;
  445.   int *off;
  446.   int *poff;
  447.   {
  448.     register int pos, nextpos, ret;
  449.     pos = -1;
  450.     nextpos = 0;
  451.     ret = 1;
  452.     while ( nextpos < block_ptr->bend)
  453.       {
  454.         ret = strcmp((char *)(pe->key),
  455.                      (char *)(ENT_ADR(block_ptr, nextpos)->key));
  456.     if (ret <= 0) break;
  457.         pos = nextpos;
  458.     nextpos += ENT_SIZE(ENT_ADR(block_ptr,pos));
  459.     /* nextpos = next_entry(pos); */
  460.       }
  461.     *poff = pos;
  462.     if (ret == 0) *off = nextpos;
  463.     else *off = pos;
  464.     CO(pci->level) = *off;
  465.     return (ret);
  466.   } /* find_block */
  467.  
  468.  
  469. void pascal movedown(pb, off, n)       /* move part of block downward */
  470.   BLOCK *pb;                           /* block to move down */
  471.   int off;                             /* start move here */
  472.   int n;                               /* move this far */
  473.   {
  474.     memmove(ENT_ADR(pb, off),
  475.            ENT_ADR(pb, off + n),
  476.            pb -> bend - (off + n));
  477.   } /* movedown */
  478.  
  479.  
  480. void pascal moveup(pb, off, n)        /* move part of a block upward */
  481.   BLOCK *pb;                          /* the block */
  482.   int off;                            /* start move here */
  483.   int n;                              /* move up n bytes */
  484.   {
  485.     memmove(ENT_ADR(pb, off + n),
  486.             ENT_ADR(pb, off),
  487.             pb->bend - off);
  488.   } /* moveup */
  489.  
  490.  
  491. void pascal ins_block(pb, pe, off)      /* insert entry into a block */
  492.   BLOCK *pb;                            /* add to this block */
  493.   ENTRY *pe;                            /* add this entry */
  494.   int off;                              /* at this position */
  495.   {
  496.     int size;
  497.     size = ENT_SIZE(pe);                /* size of new entry */
  498.     moveup(pb,off,size);                /* move entries to make room */
  499.     copy_entry(ENT_ADR(pb,off),pe);     /* copy new entry */
  500.     pb->bend += size;                   /* adjust block size */
  501.   } /* ins_block */
  502.  
  503.  
  504. void pascal del_block(pb, off)          /* delete entry in a block */
  505.   BLOCK *pb;                            /* this block */
  506.   int off;                              /* delete entry at this position */
  507.   {
  508.     int ne;
  509.     ne = ENT_SIZE(ENT_ADR(pb, off));   /* size of deleted entry */
  510.     movedown(pb, off, ne);             /* move entries down */
  511.     pb->bend -= ne;                    /* adjust block size */
  512.   } /* del_block */
  513.  
  514.  
  515. /*  position at start/end of index  */
  516.  
  517. int cdecl first_key(pe, pix)          /* return first key */
  518.   ENTRY *pe;
  519.   IX_DESC *pix;                       /* in this index file */
  520.   {
  521.     int ret;
  522.  
  523.     pci = pix;                        /* set global index descriptor */
  524.     block_ptr = &(pci->root);         /* start with the root */
  525.     CB(0) = 0L;                       /* root address is 0L */
  526.     CO(0) = -1;                       /* offset is -1 */
  527.     pci->level = 0;                   /* 0 level in index file */
  528.     while(block_ptr->p0 != NULLREC)   /* repeat for all levels */
  529.       {                               /* get index block for next level */
  530.         retrieve_block(++(pci->level), block_ptr->p0);
  531.         CO(pci->level) = -1;          /* position to start of block */
  532.       }
  533.     ret = prev_key(pe, pix);          /* get first key */
  534.     return ( ret );
  535.   } /* first_key */
  536.  
  537.  
  538. int cdecl last_key(pe, pix)           /* return last key */
  539.   ENTRY *pe;
  540.   IX_DESC *pix;                       /* in this index file */
  541.   {
  542.     long  ads;
  543.     int   ret;
  544.  
  545.     pci = pix;
  546.     block_ptr = &(pci->root);         /* start with the root */
  547.     CB(0) = 0L;
  548.     pci->level = 0;
  549.     if(last_entry() >= 0)             /* repeat for all levels */
  550.       {                               /* get block for next level */
  551.         while ((ads = ENT_ADR(block_ptr,last_entry())->idxptr) != NULLREC)
  552.              retrieve_block(++(pci->level), ads);
  553.       }
  554.     CO(pci->level) = block_ptr->bend; /* set offset position to the end */
  555.     ret = prev_key(pe, pix);          /* get last key */
  556.     return ( ret );
  557.   } /* last_key */
  558.  
  559.  
  560. /*  get next, previous entries  */
  561.  
  562. int cdecl next_key(pe, pix)           /* get next key */
  563.   ENTRY *pe;                          /* and put it here */
  564.   IX_DESC *pix;                       /* for this index */
  565.   {
  566.     RECPOS  address;
  567.     pci = pix;
  568.                                       /* get block for current level */
  569.     retrieve_block(pci->level, CB(pci->level));
  570.                                       /* set address for next level */
  571.     if(CO(pci->level) == -1) address = block_ptr->p0;
  572.     else
  573.       {
  574.         if (CO(pci->level) == block_ptr->bend) address = NULLREC;
  575.         else address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  576.       }
  577.     while (address != NULLREC)        /* repeat until at leaf level */
  578.       {
  579.          retrieve_block(++(pci->level), address);
  580.          CO(pci->level) = -1;
  581.          address = block_ptr->p0;
  582.       }
  583.     next_entry(CO(pci->level));       /* get next entry for leaf block */
  584.     if (CO(pci->level) == block_ptr->bend)   /* check for end of block */
  585.       {
  586.         do
  587.           { if(pci->level == 0)       /* if this is the root block */
  588.               {
  589.                 return (EOIX);        /* return end of index file */
  590.               }
  591.             --(pci->level);           /* level of ancestor block */
  592.             retrieve_block(pci->level, CB(pci->level));
  593.             next_entry(CO(pci->level));  /* next entry for ancestor */
  594.           } while (CO(pci->level) == block_ptr->bend);
  595.       }
  596.                                       /* copy the next entry and return */
  597.     copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  598.     return ( IX_OK );
  599.   } /* next_key */
  600.  
  601.  
  602. int cdecl prev_key(pe, pix)          /* get the previous key */
  603.   ENTRY *pe;                         /* put it here */
  604.   IX_DESC *pix;                      /* for this index */
  605.   {
  606.     RECPOS  address;
  607.     pci = pix;
  608.                                      /* get block for current level */
  609.     retrieve_block(pci->level, CB(pci->level));
  610.     prev_entry(CO(pci->level));      /* previous entry in this block */
  611.     if (CO(pci->level) == -1)
  612.       address = block_ptr->p0;
  613.     else
  614.       address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  615.     if (address != NULLREC)          /* go to the leaf level of index */
  616.       { do
  617.           {
  618.             retrieve_block(++(pci->level), address);
  619.             address = ENT_ADR(block_ptr, last_entry())->idxptr;
  620.           } while (address != NULLREC);
  621.       }
  622.     if (CO(pci->level) == -1)        /* check if at beginning of block */
  623.       { do
  624.           {
  625.             if(pci->level == 0)      /* if this is the root block */
  626.               {
  627.                 return (EOIX);       /* and return end of index */
  628.               }
  629.             --(pci->level);          /* level for ancestor block */
  630.           } while (CO(pci->level) == -1);   /* repeat if beginning */
  631.         retrieve_block(pci->level, CB(pci->level));   /* get block  */
  632.       }
  633.                                      /* copy entry and return */
  634.     copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  635.     return ( IX_OK );
  636.   } /* prev_key */
  637.  
  638.  
  639. /*  insert new entries into tree  */
  640.  
  641. void pascal split(l, pe, e)           /* split an index block */
  642.   int l;                              /* level in tree */
  643.   ENTRY *pe;                          /* entry to insert */
  644.   ENTRY *e;                           /* entry to pass up to next level */
  645.   {
  646.     int  half, ins_pos, size;
  647.     ins_pos = CO(pci->level);         /* save current offset */
  648.                                       /* and divide block in half */
  649.     half = scan_blk(block_ptr->bend / 2 + sizeof(RECPOS));
  650.     if (half == ins_pos)              /* if inserting at half */
  651.       *e = *pe;                       /* pass up entry pe */
  652.     else                              /* else copy entry at half */
  653.       {
  654.          copy_entry(e, ENT_ADR(block_ptr, half));
  655.          size = ENT_SIZE(e);
  656.          movedown(block_ptr, half, size);   /* move block entries down */
  657.          block_ptr->bend -= size;           /* and adjust the size */
  658.       }
  659.     spare_block = &BUFBLOCK(new_cache());   /* allocate a spare block */
  660.     memmove(spare_block->entries,           /* and copy half the entries */
  661.            ENT_ADR(block_ptr,half),
  662.            block_ptr->bend - half);
  663.     spare_block->brec = get_free();         /* index address of new block */
  664.     spare_block->bend = block_ptr->bend - half;    /* set size of block */
  665.     spare_block->p0 = e->idxptr;            /* set all the pointers */
  666.     block_ptr->bend = half;
  667.     e->idxptr = spare_block->brec;
  668.     if (ins_pos < half)                     /* insert the new entry */
  669.       ins_block(block_ptr,pe,ins_pos);      /* in current block */
  670.     else if (ins_pos > half)                /* else insert the entry */
  671.       {                                     /* in the spare block */
  672.          ins_pos -= ENT_SIZE(e);
  673.          ins_block(spare_block,pe,ins_pos - half);
  674.          CB(l) = e->idxptr;                 /* set block address */
  675.          CO(l) = CO(l) - half;              /* and offset */
  676.       }
  677.     write_if(pci->ixfile, spare_block->brec,   /* write to disk */
  678.              (char *) spare_block, sizeof(BLOCK));
  679.   } /* split */
  680.  
  681.  
  682. void pascal ins_level(l, e)        /* insert an entry e */
  683.   int l;                           /* into block level l */
  684.   ENTRY *e;
  685.   {
  686.     int  i;
  687.     if ( l < 0)                    /* tree height has increased */
  688.       {  for (i = 1; i < MAX_LEVELS; i++)   /* save offset and addresses */
  689.            {  CO(MAX_LEVELS - i) = CO(MAX_LEVELS - i - 1);
  690.               CB(MAX_LEVELS - i) = CB(MAX_LEVELS - i - 1);
  691.            }
  692.                                    /* copy old root to spare block */
  693.          memmove(spare_block, &(pci->root), sizeof(BLOCK));
  694.                                   /* get index address and write to disk */
  695.          spare_block->brec = get_free();
  696.          write_if(pci->ixfile, spare_block->brec,
  697.                   (char *) spare_block, sizeof(BLOCK));
  698.          pci->root.p0 = spare_block->brec;    /* set p0 pointer */
  699.          copy_entry((ENTRY *) (pci->root.entries), e);  /* copy insert e */
  700.          pci->root.bend = ENT_SIZE(e);        /* root contains only e */
  701.          CO(0) = 0;                           /* root offset is 0 */
  702.          pci->level = 0;                      /* set current level */
  703.          (pci->dx.nl)++;                      /* increment no. of levels */
  704.      pci->root_dirty = TRUE;
  705.       }
  706.     else ins_block(block_ptr,e,CO(l));        /* insert in current block */
  707.   } /* ins_level */
  708.  
  709.  
  710. int pascal insert_ix(pe, pix)         /* insert at current level */
  711.   ENTRY *pe;                          /* insert entry pe */
  712.   IX_DESC *pix;                       /* into this index */
  713.   {
  714.     ENTRY    e, ee;
  715.     int h;
  716.     h = 0;
  717.     pci = pix;
  718.     ee = *pe;
  719.     do
  720.       {
  721.          if(CO(pci->level) >= 0)      /* set new offset */
  722.            CO(pci->level) +=
  723.                   ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level)));
  724.          else
  725.            CO(pci->level) = 0;
  726.          update_block();           /* we are going to change this block */
  727.                                    /* if new block size < split size */
  728.          if( (block_ptr->bend + ENT_SIZE(&ee)) <= split_size)
  729.            {
  730.              ins_level(pci->level, &ee);   /* insert into current block */
  731.              break;                        /* and break */
  732.            }
  733.          else
  734.            {
  735.              h = 1;                        /* must reset index pointers */
  736.              split(pci->level,&ee, &e);    /* split the current block */
  737.              ee = e;                       /* this entry is passed up */
  738.              pci->level--;                 /* to insert at this level */
  739.              if (pci->level < 0)           /* increase tree height */
  740.                {
  741.                  ins_level(pci->level, &e);
  742.                  break;
  743.                }
  744.                                            /* get block for next level */
  745.              retrieve_block(pci->level, CB(pci->level));
  746.            }
  747.       }
  748.     while (1);
  749.     if (h) find_ix(pe, pix, 0);           /* reset pointers if necessary */
  750.     return ( IX_OK );
  751.   } /* insert_ix */
  752.  
  753.  
  754. /*  BPLUS find and add key functions  */
  755.  
  756. int pascal find_ix(pe, pix, find)     /* search an index file */
  757.   ENTRY *pe;                          /* for this entry */
  758.   IX_DESC *pix;                       /* in this index */
  759.   int find;                           /* 1 to add_key, 0 to find_key */
  760.   {
  761.     int      level, off, poff, ret;
  762.     int      savelevel, saveoff, h;
  763.     RECPOS   ads, saveads;
  764.     pci = pix;
  765.     ads = 0L;
  766.     level = 0;
  767.     h = 0;
  768.     while (ads != NULLREC)
  769.       {  pci->level = level;
  770.          retrieve_block(level, ads);
  771.      if (find_block(pe, &off, &poff) == 0) ret = 1;
  772.      else ret = 0;
  773.      if (ret && find && !pci->duplicate) break;
  774.      if(ret && pci->duplicate)
  775.      {
  776.        saveads = ads;
  777.        savelevel = level;
  778.        saveoff = off;
  779.        off = poff;
  780.        h = 1;
  781.      }
  782.          if (off == -1)
  783.            ads = block_ptr->p0;
  784.          else
  785.        ads = ENT_ADR(block_ptr, off)->idxptr;
  786.          CO(level++) = off;
  787.        }
  788.      if (h && find)
  789.      {
  790.        if (!ret)
  791.        {
  792.      retrieve_block(savelevel, saveads);
  793.      pci->level = savelevel;
  794.      ret = 1;
  795.        }
  796.        CO(savelevel) = saveoff;
  797.      }
  798.      return ( ret );
  799.    } /* find_ix */
  800.  
  801.  
  802. int cdecl find_key(pe, pix)           /* find a key */
  803.   ENTRY *pe;                          /* this entry */
  804.   IX_DESC *pix;                       /* in this index */
  805.   {
  806.     int ret;
  807.     ret = find_ix(pe, pix, 1);       /* find_ix does all the work */
  808.                                      /* if found, copy the entry */
  809.     if ( ret ) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  810.     return ( ret );
  811.   } /* find_key */
  812.  
  813.  
  814. int cdecl add_key(pe, pix)            /* add a new key */
  815.   ENTRY *pe;                          /* this entry */
  816.   IX_DESC *pix;                       /* this index file */
  817.   {
  818.     int ret;
  819.     ret = find_ix(pe, pix, 0);        /* see if key is already in index */
  820.                                       /* if found, are dupicates are OK? */
  821.     if ( ret && (pci->duplicate == 0)) return ( IX_FAIL );
  822.     pe->idxptr = NULLREC;             /* add new key on leaf level */
  823.     return (insert_ix(pe, pix));      /* insert_ix does the work */
  824.   } /* add_key */
  825.  
  826.  
  827. int cdecl locate_key(pe, pix)         /* locate first key */
  828.   ENTRY *pe;                          /* <= this entry */
  829.   IX_DESC *pix;                       /* in this index */
  830.   {
  831.     int ret;
  832.     ret = find_ix(pe, pix, 1);        /* search index for entry */
  833.                                       /* if found, copy it to pe */
  834.     if (ret) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  835.                                       /* else get the next key */
  836.     else if (next_key(pe,pix) == EOIX) ret = EOIX;
  837.     return ( ret );
  838.   } /* locate_key */
  839.  
  840.  
  841. int cdecl find_exact(pe, pix)         /* find an exact match */
  842.   ENTRY *pe;                          /* for this entry */
  843.   IX_DESC * pix;                      /* in this index */
  844.   {
  845.     int  ret;
  846.     ENTRY e;
  847.     copy_entry(&e, pe);               /* make a copy of the entry */
  848.     ret = find_key(&e, pix);          /* is it in the index? */
  849.     if ( ret && pci->duplicate)       /* if duplicate key are allowed */
  850.       {                               /* then search for recptr match */
  851.     while (e.recptr != pe->recptr)
  852.     {
  853.       if (next_key(&e, pci) == EOIX) return (0);   /* no more records */
  854.       if (strcmp(e.key, pe->key) != 0) return (0); /* key changed */
  855.     }
  856.       }
  857.     copy_entry(pe, &e);
  858.     return ( ret );
  859.   } /* find_exact */
  860.  
  861.  
  862. /* BPLUS delete key functions */
  863.  
  864. int cdecl delete_key(pe, pix)         /* delete a key */
  865.   ENTRY *pe;                          /* this entry */
  866.   IX_DESC *pix;                       /* in this index */
  867.   {
  868.      ENTRY   e;
  869.      RECPOS  ads;
  870.      int     h, leveli, levelf;
  871.                                       /* search index for exact match */
  872.      if (!find_exact(pe, pix))  return( IX_FAIL );
  873.      h = 1;
  874.      if ((ads = pe->idxptr) != NULLREC)    /* if not the leaf level */
  875.        {
  876.           leveli = pci->level;        /* save current level */
  877.           do                          /* go to leaf level of index */
  878.             {
  879.                retrieve_block(++(pci->level), ads);
  880.                CO(pci->level) = -1;
  881.             }
  882.           while ((ads = block_ptr->p0) != NULLREC);
  883.           CO(pci->level) = 0;
  884.           copy_entry(&e, ENT_ADR(block_ptr, CO(pci->level)));
  885.           levelf = pci->level;        /* save leaf level */
  886.           pci->level = leveli;        /* reset starting level */
  887.           replace_entry(&e);          /* replace with entry from leaf */
  888.           pci->level = levelf;        /* leaf level */
  889.        }
  890.      while ( h )
  891.        {
  892.       /* get block and delete current entry */
  893.           retrieve_block(pci->level, CB(pci->level));
  894.           del_block(block_ptr, CO(pci->level));
  895.           update_block();             /* block has been changed */
  896.           if ( (pci->level == 0) && (block_ptr->bend == 0))
  897.           /* tree was reduced in height */
  898.             {
  899.               if (pci->root.p0 != NULLREC)    /* replace root block */
  900.                 {
  901.                   retrieve_block(++pci->level, pci->root.p0);
  902.                   memmove(&(pci->root), block_ptr, sizeof(BLOCK));
  903.                   (pci->dx.nl)--;           /* decrement number of levels */
  904.                   write_free(block_ptr->brec, block_ptr);  /* reuse space */
  905.                   BUFDIRTY(cache_ptr) = 0;       /* block saved on disk */
  906.                   BUFHANDLE(cache_ptr) = 0;
  907.                 }
  908.               break;
  909.             }
  910.           /* see if we can combine index blocks */
  911.           h = (block_ptr->bend < comb_size) && (pci->level > 0);
  912.           if ( h )
  913.               h = combineblk(CB(pci->level), block_ptr->bend);
  914.        }
  915.     find_ix(pe, pix, 0);         /* restore CO and CB for each level */
  916.     return( IX_OK );
  917.   } /* delete_key */
  918.  
  919.  
  920. int pascal combineblk(ads, size)      /* combine index blocks */
  921.   RECPOS ads;                         /* block at this address */
  922.   int size;                           /* and is this size */
  923.   {
  924.     ENTRY  e;
  925.     RECPOS address;
  926.     int    esize, off, ret, saveoff, ibuff;
  927.     ret = 0;
  928.                                    /* ancestor level and save offset */
  929.     saveoff = CO(--(pci->level));
  930.                                    /* retrieve ancestor index block */
  931.     retrieve_block(pci->level, CB(pci->level));
  932.     if ((off = next_entry( saveoff )) < block_ptr->bend)
  933.       /* combine with page on right */
  934.       {
  935.     if ( (int)(ENT_SIZE(ENT_ADR(block_ptr, off)) + size) < split_size)
  936.           /* okay to combine */
  937.           {
  938.             copy_entry(&e, ENT_ADR(block_ptr, off));   /* save entry */
  939.             address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  940.             retrieve_block(++pci->level, address);
  941.             ibuff = cache_ptr;           /* save cache pointer */
  942.             spare_block = block_ptr;     /* use as spare block */
  943.             retrieve_block(pci->level, ads);
  944.             esize = ENT_SIZE(&e);
  945.             if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
  946.                  && (spare_block->bend <= block_ptr->bend + esize))
  947.                return( ret );
  948.             e.idxptr = spare_block->p0;
  949.             ins_block(block_ptr, &e, block_ptr->bend);
  950.             update_block();
  951.             if ((block_ptr->bend + spare_block->bend) < split_size)
  952.             /* combine the blocks */
  953.               {
  954.                 memmove(ENT_ADR(block_ptr, block_ptr->bend),
  955.                        ENT_ADR(spare_block, 0),
  956.                        spare_block->bend);
  957.                 /* set block length and free spare block space */
  958.                 block_ptr->bend += spare_block->bend;
  959.                 write_free(spare_block->brec, spare_block);
  960.                 BUFDIRTY(ibuff) = 0;
  961.                 BUFHANDLE(ibuff) = 0;
  962.                 --pci->level;
  963.                 ret = 1;
  964.               }
  965.             else
  966.             /* move an entry up to replace the one moved */
  967.               {
  968.                 copy_entry(&e, ENT_ADR(spare_block, 0));
  969.                 esize = ENT_SIZE(&e);
  970.                 /* fixup spare block and pointers */
  971.                 movedown(spare_block, 0, esize);
  972.                 spare_block->bend -= esize;
  973.                 spare_block->p0 = e.idxptr;
  974.                 BUFDIRTY(ibuff) = 1;
  975.                 --(pci->level);
  976.                 replace_entry(&e);
  977.               }
  978.           }
  979.       }
  980.     else
  981.       /* move from page on left */
  982.       {
  983.     if ( (int)(ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level))) + size)
  984.                  < split_size)
  985.           /* okay to proceed */
  986.           {
  987.             copy_entry(&e, ENT_ADR(block_ptr, saveoff));  /* save entry */
  988.             /* get page which is on the left */
  989.             off = prev_entry(saveoff);
  990.             if (CO(pci->level) == -1) address = block_ptr->p0;
  991.             else address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  992.             retrieve_block(++pci->level, address);
  993.             off = last_entry();
  994.             ibuff = cache_ptr;
  995.             /* set spare block to left page */
  996.             spare_block = block_ptr;
  997.             /* get current block */
  998.             retrieve_block(pci->level, ads);
  999.             esize = ENT_SIZE(&e);
  1000.             if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
  1001.                  && (spare_block->bend <= block_ptr->bend + esize))
  1002.                return( ret );
  1003.             BUFDIRTY(ibuff) = 1;           /* we have changed things */
  1004.             CO(pci->level) = 0;
  1005.             e.idxptr = block_ptr->p0;
  1006.             ins_block(block_ptr, &e, 0);
  1007.             if ((block_ptr->bend + spare_block->bend) < split_size)
  1008.             /* combine the blocks */
  1009.               {
  1010.                 memmove(ENT_ADR(spare_block, spare_block->bend),
  1011.                        ENT_ADR(block_ptr, 0),
  1012.                        block_ptr->bend);
  1013.                 /* set block length and freeup block */
  1014.                 spare_block->bend += block_ptr->bend;
  1015.                 write_free(block_ptr->brec, block_ptr);
  1016.                 BUFDIRTY(cache_ptr) = 0;
  1017.                 BUFHANDLE(cache_ptr) = 0;
  1018.                 CO(--(pci->level)) = saveoff;
  1019.                 ret = 1;
  1020.               }
  1021.             else
  1022.             /* move an entry up to replace the one moved */
  1023.               {
  1024.                  block_ptr->p0 = ENT_ADR(spare_block,off)->idxptr;
  1025.                  copy_entry(&e, ENT_ADR(spare_block, off));
  1026.                  spare_block->bend = off;
  1027.                  update_block();
  1028.                  CO(--(pci->level)) = saveoff;
  1029.                  replace_entry(&e);
  1030.               }
  1031.           }
  1032.       }
  1033.     return ( ret );
  1034.   } /* combineblk */
  1035.  
  1036.  
  1037. void pascal replace_entry(pe)     /* replace entry at current position */
  1038.   ENTRY *pe;                      /* with this entry */
  1039.   {
  1040.     retrieve_block(pci->level, CB(pci->level));   /* get current block */
  1041.     /* set address for the replacement entry */
  1042.     pe->idxptr = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  1043.     del_block(block_ptr, CO(pci->level));      /* now delete the entry */
  1044.     prev_entry(CO(pci->level));                /* backup one entry */
  1045.     insert_ix(pe, pci);                        /* and insert new entry */
  1046.     update_block();
  1047.   } /* replace_entry */
  1048.  
  1049.